package com.jiang.daily.Q2944;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/24 20:10
 */
class Solution {
    // // 使用map充当记忆数组
    // Map<Integer, Integer> memo = new HashMap<Integer, Integer>();
    // int[] prices;

    // // 题目有误：如果你花费 prices[i] 购买了下标为 i 的水果，那么你可以免费获得下标范围在 [i + 1, 2 * i + 1] 的水果。
    // public int minimumCoins(int[] prices) {
    //     this.prices = prices;
    //     return dp(0);
    // }

    // private int dp(int index) {
    //     if (2 * index + 2 >= prices.length) return prices[index];

    //     if (memo.containsKey(index)) return memo.get(index);

    //     int min = Integer.MAX_VALUE;
    //     for (int i = index + 1; i <= 2 * index + 2; i++) {
    //         min = Math.min(min, dp(i));
    //     }

    //     return prices[index] + min;
    // }

    public int minimumCoins(int[] prices) {
        int n = prices.length;
        Deque<int[]> queue = new ArrayDeque<int[]>();
        queue.offerFirst(new int[]{n, 0});
        for (int i = n - 1; i >= 0; i--) {
            while (2 * i + 2 < queue.peekLast()[0]) {
                queue.pollLast();
            }
            int cur = prices[i] + queue.peekLast()[1];
            while (cur <= queue.peekFirst()[1]) {
                queue.pollFirst();
            }
            queue.offerFirst(new int[]{i, cur});
        }
        return queue.peekFirst()[1];
    }
}

